package study.datastructure.order.recursion;/**
 * @program: datastructure
 * @author: lcy
 * @create: 2024-09-27 22:37
 */

import java.util.Arrays;

/**
 2024/9/27,
 */

//斐波那契数列及优化
public class Fibonacci {

    //求解f(n)
    public static int f1(int n){
        if (n==1) return 1;
        if (n==0) return 0;

        int x= f1(n-1);
        int y=+f1(n-2);
        return x+y;
    }
  //求解f(n)
    static int[] cache;
    public static int f(int n){
        cache=new int[n+1]; //n=5
        Arrays.fill(cache,-1); //{-1,-1,-1,-1,-1,-1}
        cache[0]=0;
        cache[1]=1;
        return f2(n);

    }
    private static int f2(int n){
        if (cache[n]!=-1){
            return cache[n];
        }

        int x= f2(n-1);
        int y=+f2(n-2);
        cache[n]=x+y;
        return x+y;
    }
}
